package com.algrithom.graph.mincreatetree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import com.common.model.Edge;
import com.common.model.WeightGraph;

/**
 * 最小生成树问题-Lazy Prim算法
 * 边集数组
 *
 * @author think
 * @version 1.0.0
 * @since 2020/3/14
 */
public class LazyPrimMst {
    
    private final PriorityQueue<Edge> minHeap;
    
    private final boolean[] marked;
    
    private final List<Edge> mst = new ArrayList<>();
    
    public LazyPrimMst(WeightGraph graph){
        // 构造Edge的最小堆
        minHeap = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
        marked = new boolean[graph.getNodeNum()];
        
        // Lazy Prim
        // 1. 首先访问第0个顶点
        visit(graph,0);
        // 2. minHeap不为空时进行MST的收集
        while (!minHeap.isEmpty()) {
            Edge minEdge = minHeap.poll();
            // 这条边两端都被访问过，则抛弃
            if (marked[minEdge.getSrcNode()] && marked[minEdge.getDstNode()]) {
                continue;
            }
            mst.add(minEdge);
            // 继续在未访问过的顶点进行访问
            if (!marked[minEdge.getSrcNode()]) {
                visit(graph,minEdge.getSrcNode());
            } else {
                visit(graph,minEdge.getDstNode());
            }
        }
    }
    
    public static void main(String[] args){
        WeightGraph graph = new WeightGraph();
        Edge edge = new Edge(0,1,8);
        graph.getEdges().add(edge);
        edge = new Edge(0,2,9);
        graph.getEdges().add(edge);
        edge = new Edge(0,3,5);
        graph.getEdges().add(edge);
        edge = new Edge(1,2,7);
        graph.getEdges().add(edge);
        edge = new Edge(2,3,6);
        graph.getEdges().add(edge);
        graph.setNodeNum(4);

        // 获取mst
        LazyPrimMst lazyPrimMst = new LazyPrimMst(graph);
        System.out.println(lazyPrimMst.getMst());
        System.out.println(lazyPrimMst.getWeight());
    }
    
    public List<Edge> getMst(){
        return mst;
    }
    
    public int getWeight(){
        // 将mst中的权值累加返回
        return mst.stream().mapToInt(Edge::getWeight).sum();
    }
    
    private void visit(WeightGraph graph,int node){
        if (marked[node] || node >= graph.getNodeNum()) {
            return;
        }
        // 访问标示
        marked[node] = true;
        // 将v尚未访问过的邻边加入到最小堆中（横切边）
        for (Edge edge : graph.getEdges()) {
            // 改变的另一个节点一定不可被访问过，否则不是横切边
            if (!marked[edge.getOther(node)]) {
                minHeap.offer(edge);
            }
        }
    }
}
